МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління / Лабораторна робота №7-8 з дисципліни “Математичні методи дослідження операцій” на тему « Транспортна задача. Метод потенціалів»  Львів – 2012 Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel, вивчення та оволодіння навиками розв’язання оптимізаційних задач в середовищі MathCad, набуття навиків розв’язку транспортної задачі за допомогою математичних пакетів та розробки оригінальної програми. План Короткі теоретичні відомості. Постановка задачі Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом північно-західного кута (ПЗК) і розв’язання транспортної задачі методом потенціалів. Знаходження базового рішення закритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів. Знайти базове рішення відкритої транспортної задачі (ТЗ) шляхом найменшої вартості (НВ) і розв’язання транспортної задачі методом потенціалів. Розв’язання за допомогою пакету програм MS Exel. Розв’язання за допомогою пакету програм Optimal 1_4 Розв’язання за допомогою власної програми. Хід роботи 1. Короткі теоретичні відомості Постановка транспортної задачі В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1( i ( m, 1 ( j ( n. Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами. Умови Т-задачі записуються у вигляді ai С =

bj b1 b2 b3 … bn Введемо змінні хij ( 0, 1( i ( m, 1 ( j ( n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва ( ai ) в j пункт споживання ( bj ). Необхідно знайти множину значень змінних хij ( 0, мінімізуючи функцію L =
, з виконанням умов
Матрицю Х =
називають планом перевезень Т-задачі. Визначення початкового опорного плану. Метод «північно-західного кута» (ПЗК). Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута. Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n. Припустимо, що вже виконано t кроків. Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай ( + ( = t + 2. Знаходимо x(( = min{
}, де
. Якщо
, то заповнюється (-ий рядок матриці, починаючи з ((+1)-го елемента, нулями. Якщо
, то заповнюється нулями (-й стовбець, починаючи з ((+1)-ї строки. При цьому
;
Метод потенціалів розв’язування транспортної задачі. Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій. Попередній етап. 1. Будується початковий опорний план Х0. 2. Обчислюється оціночна матриця Δ1 =
, де ui i vj – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова
для хij ( 0 (базових клітин). Для зручності вибирається u1 = 0. Позиція в матриці Δ1, яка відпов...